package com.demo.jzoffer2;

import com.demo.domain.TreeNode;
import org.junit.Test;

import java.util.HashMap;

/**
 * @author gy
 * @date 2023/01/12
 */
public class Test0202_02 {
    /**
     * 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
     *
     * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
     *
     * Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
     * Output: [3,9,20,null,null,15,7]
     *
     * Input: preorder = [-1], inorder = [-1]
     * Output: [-1]
     * @param preorder
     * @param inorder
     * @return
     */
    HashMap<Integer, Integer> map = new HashMap<>();// 通过map来查找中序遍历对应的索引
    int[] preorder;// 保留先序遍历，方便递归时依据索引查找线序遍历的值

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        // 将中序遍历的值 及 索引放在map中，方便递归时获取左子树 与 右子树的数量 以及根的索引
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        // 三个索引分别
        // 当前根的索引
        // 递归树 的左边界 数组左边界
        // 递归树 的右边界 数组右边界
        // 先序遍历口诀  根左右
        return recur(0,0,inorder.length-1);
    }

    TreeNode recur(int pre_root, int in_left, int in_right){
        if(in_left > in_right) return null; // 左右边界相等时，就是自己
        TreeNode root = new TreeNode(preorder[pre_root]); // 获取root节点 先序遍历的第一个节点
        int idx = map.get(preorder[pre_root]); // 通过先序遍历中根节点的值，获取到在中序遍历中根节点的索引值
        // 开始补充 root节点的左子树
        // 左子树的根的索引值 先序中的根节点 + 1
        // 递归左子树的左边界 为 原来的中序的 in_left
        // 递归左子树的左边界 为 原来的中序的 根节点索引 -1
        root.left = recur(pre_root+1, in_left, idx-1);
        // 开始补充 root节点的右子树
        // 右子树的根的索引为先序中的 当前根的位置 + 左子树的数量 + 1
        // 递归右子树的左边界为中序中当前根节点+ 1
        // 递归右子树的有边界为中序中原来右子树的边界
        root.right = recur(pre_root + (idx - in_left) + 1, idx+1, in_right);
        return root;

    }

    @Test
    public void m1() {
    }

    @Test
    public void m2() {

    }

}
